package 平衡二叉树;

/**
 * @author: zhengtao
 * @description: 平衡二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 * @version: 1.0
 * @date: 2022/10/30  14:11
 */
public class Demo110 {


     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }
     }

    public boolean isBalanced(TreeNode root) {
        if(root!=null){
            //根的左右节点小于2，根的左右子节点也要满足平衡二叉树
            return  (Math.abs(getDepth(root.right)-getDepth(root.left))<2)&&isBalanced(root.left)&&isBalanced(root.right) ;
        }else{
            return true;
        }
    }
    //求高度,递归三部曲
    private int getDepth(TreeNode root) {
          if(root==null){
              return 0;
          }
          return Math.max(getDepth(root.left),getDepth(root.right))+1;
    }
}
